package com.peng.leetcode.slidingWindow;

import java.util.LinkedList;

/**
 * MaxSlidingWindow
 * 剑指 Offer 59 - I. 滑动窗口的最大值
 * https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
 *
 * @author: lupeng6
 * @create: 2023/2/24 11:09
 */
public class MaxSlidingWindow1 {

    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        int[] ans = new int[nums.length - k + 1];
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            while (!queue.isEmpty() && nums[i] >= nums[queue.peekLast()]) {
                queue.pollLast();
            }
            queue.offerLast(i);
            int left = i - k + 1;
            while (queue.peekFirst() < left) {
                queue.pollFirst();
            }
            if (i + 1 >= k) {
                ans[left] = nums[queue.peekFirst()];
            }
        }
        return ans;
    }



}
